CODE 140. Reorder List

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/25/2013-11-25-CODE 140 Reorder List/

访问原文「CODE 140. Reorder List」

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes’ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

public void reorderList(ListNode head) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	if (null == head) {
		return;
	}
	ListNode tmpHead = head;
	int size = 0;
	while (tmpHead != null) {
		size++;
		tmpHead = tmpHead.next;
	}
	Queue<ListNode> q = new LinkedList<ListNode>();
	Stack<ListNode> s = new Stack<ListNode>();

	tmpHead = head;
	for (int i = 0; i < (size + 1) / 2; i++) {
		q.offer(tmpHead);
		tmpHead = tmpHead.next;
	}
	while (tmpHead != null) {
		s.push(tmpHead);
		tmpHead = tmpHead.next;
	}
	ListNode newNode = new ListNode(0);
	ListNode newTmpNode = newNode;
	while (!q.isEmpty() && !s.isEmpty()) {
		newTmpNode.next = q.poll();
		newTmpNode = newTmpNode.next;
		newTmpNode.next = s.pop();
		newTmpNode = newTmpNode.next;
	}
	if (!q.isEmpty()) {
		newTmpNode.next = q.poll();
		newTmpNode = newTmpNode.next;
	}
	newTmpNode.next = null;
	head = newNode.next;
}